This invention relates to a method and apparatus for tiling an image.
In a computer graphics system, an image is displayed on the screen of a cathode-ray-tube (CRT) or other display device Generally, the electron beam of the CRT is deflected under control of a digital signal having an X (horizontal) component and a Y (vertical) component, so that pixels on a rectangular array of grid points are addressed row-by-row in accordance with a raster pattern. Data representing the image is generated in a processor and is down-loaded from the processor to a frame buffer. The frame buffer has memory locations which correspond on a one-to-one basis with the grid points of the CRT display In the following description, it will be assumed for the sake of clarity that the memory locations of the frame buffer are physically arranged in a rectangular array which corresponds to the array of grid points of the display
The digital signal that is used-.to control deflection of the CRT's electron beam is also used to control addressing of the frame buffer, and the color with which the pixel at a grid point is displayed depends on the contents of the corresponding memory location. The frame buffer thus contains a virtual image of the display that is provided by the CRT. The data provided to the frame buffer by the processor may represent an image composed of colored areas. The process of loading data values into the frame buffer memory to represent a colored area is called tiling. In the following description, references are made in connection with a tiling operation to the tiling of specified grid points and to the tiling of polygons. However, this is intended merely as an abbreviated way of referring to the tiling of the memory locations corresponding to the specified grid points and to the tiling of the memory locations corresponding to the grid points that lie within the polygons.
A computer graphics system may be used to depict a three-dimensional object having polygonal surfaces by projection of those surfaces into a two-dimensional display plane. Each polygonal surface forms a polygon or a line when projected into the display plane. Information defining the polygonal surfaces in threedimensional space is specified to the processor, which utilizes that information to generate information defining the corresponding display plane polygons. This information is made available by the processor to a tiling engine. For each polygon in turn, the tiling engine determines which grid points lie inside the polygon. It is very time consuming to examine each grid point and determine whether it lies inside the polygon. A convex polygon may be tiled more rapidly by determining, for each row of grid points, the two locations at which that row intersects the boundary of the polygon and tiling the grid points between these locations. For example, the polygon shown in FIG. 1 may be tiled from the lowest row of grid points upwards by determining which points lie between the two edges that extend upwards from the lowest row, and tiling the corresponding memory locations. The X coordinates of the intersections of the edge AB with the grid rows 1-4 can be identified by iteratively adding the slope of the edge AB to the X coordinate of the start point A. (Since the independent variable is plotted in the Y direction, the slope of the edge AB is not (Y.sub.B -Y.sub.A)/X.sub.B -X.sub.A) but (X.sub.B -X.sub.A)/(Y.sub.B -Y.sub.A)). Similarly, the X coordinates of the intersections of the line AD with the grid rows 1-8 can be identified by iteratively adding the slope of the edge AD to the X coordinate of the start point A. On each of the rows 1-4, the grid points that lie between the two intersections of the grid row with the lines AB and AD respectively are tiled. However, the coordinates of the points A and D are (8,0) and (12,8) and therefore the slope of the edge AD is not an integer and intersections of the edge AD with the grid rows 1, 2, 3, etc. are at 81/2, 9, 91/2, 10, etc., and when determining which points to tile on alternate rows it is necessary to round the fractions up (or down) nevertheless, the eight iterations needed to reach row 8 would yield an X coordinate of 12.
The slope of an edge between two grid points cannot always be expressed as the sum of an integer (which may be zero) and a binary fraction. The slope of the edge BC is 4/11. If 4/11 is iteratively added to the X coordinate of the start point B, the values 4/11, 8/11, 1 1/11, etc. are returned. However, since the fraction 4/11 cannot be expressed accurately as a binary fraction, it is necessary to perform a division and truncation before carrying out the additions. If, for example, the fraction 4/11 were approximated by 3/8, the eleven additions required to reach the row 15 from row 4 would return 41/8. The coordinates (41/8,15) would be approximated by (4,15), so that no error would result. However, in some cases it may be necessary to carry out a hundred or more additions, in which case an error might result such that the end point that is reached by iterative addition of the slope of the edge is spaced by several grid points from the desired grid point. Accordingly, the displayed image would be inaccurate.